#include<stdio.h>
#include<stdlib.h>
#include<stack>
using namespace std;
#define maxSize 100
typedef struct tnode{
	int val;
	struct tnode *left, *right; 
}*tree;

tree Create(int A[], int n){
	if(n == 0) return 0;
	struct tnode *root = (struct tnode *)malloc(sizeof(struct tnode));
	tnode *p = root;
	stack<tree> s;
	int i = 0;
	while(p || !s.empty()){//p点赋值成功or栈非空
		if(p != NULL){
			if(A[i] == 0){		//一直创建p节点的左右孩子，直到p为空 
				p->val=i;
				p->left = NULL;
				p->right = NULL;
			}
			else if(A[i] == 1){
				struct tnode *temp = (struct tnode *)malloc(sizeof(struct tnode));
				p->val=i;
				p->left = temp;
				p->right = NULL;
			}
			else{
				struct tnode *temp1 = (struct tnode *)malloc(sizeof(struct tnode));
				struct tnode *temp2 = (struct tnode *)malloc(sizeof(struct tnode));
				p->val=i;
				p->left = temp1;
				p->right = temp2;
			}
			s.push(p);		//入栈并访问左孩子 
			p = p->left;
			i++;
		}
		else{   //当前p为空时，说明其根节点已经被访问过，现在访问其右子树节点 
			p=s.top();
            s.pop();			
			p = p->right;
		}
	} 
	return root;
}
void preOrder_Iterative(tree root){
    if(NULL==root)
        return;
    stack<tree> nodeStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        tree node=nodeStack.top();
        printf("%d ",node->val);
        nodeStack.pop();
        if(node->right) nodeStack.push(node->right);
        if(node->left) nodeStack.push(node->left);
    }
}
void InOrder_Iterative(tree root){
    if(NULL==root)
        return;//空树
    stack<tree>nodeStack;
    tree curNode=root;//维护一个当前节点指针
    //当前节点指针非空，或栈非空时迭代处理
    while(curNode||!nodeStack.empty()){
        //当前节点非空，沿着左子树方向入栈
        while(curNode){
            nodeStack.push(curNode);
            curNode=curNode->left;
        }
        //此时栈顶没有左子树，或者左子树已经访问完
        curNode=nodeStack.top();//取栈顶节点
        printf("%d ",curNode->val);//访问栈顶节点
        nodeStack.pop();//从栈中删除被访问元素
        curNode=curNode->right;//当前节点设为右节点
    }
}
void PostOrder_Iterative(tree root){
    if(NULL==root)
        return ;
    stack<tree> nodeStack;
    stack<tree> resStack;
    nodeStack.push(root);
    while(!nodeStack.empty()){
        tree node=nodeStack.top();//保存栈顶节点，便于寻找左右孩子
        resStack.push(node);
        nodeStack.pop();
        if(node->left) nodeStack.push(node->left);
        if(node->right) nodeStack.push(node->right); 
    }
    while(!resStack.empty()){
        printf("%d ",resStack.top()->val);
        resStack.pop();
    }
}
int main(int argc,const char* argv[]){
    int a[]={2,1,2,0,0,1,1,0};
    tree root=Create(a,8);
	printf("先序遍历:");
	preOrder_Iterative(root);
	printf("\n中序遍历:");
	InOrder_Iterative(root);
	printf("\n后序遍历:");
	PostOrder_Iterative(root);
    return 0;
}